package zcw.com.lib_leet_code;

import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import zcw.com.lib_leet_code.bean.TreeNode;
import zcw.com.lib_leet_code.util.Util;

/**
 * Created by 朱城委 on 2021/7/22.<br><br>
 *
 * 打家劫舍 III
 */
public class Topic337 {
    public static void main(String[] args) {
        Topic337 instance = new Topic337();

        List<Integer> list = Arrays.asList(3,2,3,null,3,null,1);
        TreeNode root = Util.createTree(list);
        System.out.println(instance.rob(root));

        list = Arrays.asList(3,4,5,1,3,null,1);
        root = Util.createTree(list);
        System.out.println(instance.rob(root));

        list = Arrays.asList(79,99,77,null,null,null,69,null,60,53,null,73,11,null,null,null,62,27,62,null,null,98,50,null,null,90,48,82,null,null,null,55,64,null,null,73,56,6,47,null,93,null,null,75,44,30,82,null,null,null,null,null,null,57,36,89,42,null,null,76,10,null,null,null,null,null,32,4,18,null,null,1,7,null,null,42,64,null,null,39,76,null,null,6,null,66,8,96,91,38,38,null,null,null,null,74,42,null,null,null,10,40,5,null,null,null,null,28,8,24,47,null,null,null,17,36,50,19,63,33,89,null,null,null,null,null,null,null,null,94,72,null,null,79,25,null,null,51,null,70,84,43,null,64,35,null,null,null,null,40,78,null,null,35,42,98,96,null,null,82,26,null,null,null,null,48,91,null,null,35,93,86,42,null,null,null,null,0,61,null,null,67,null,53,48,null,null,82,30,null,97,null,null,null,1,null,null);
        root = Util.createTree(list);
        System.out.println(instance.rob(root));
    }

    public int rob(TreeNode root) {
        return realRob(root, new HashMap<>());
    }

    private int realRob(TreeNode root, Map<TreeNode, Integer> map) {
        if(root == null) {
            return 0;
        }

        if(map.get(root) != null) {
            return map.get(root);
        }

        // 获取打劫根节点的结果
        int resultRoot = root.val;
        if(root.left != null) {
            resultRoot += realRob(root.left.left, map) + realRob(root.left.right, map);
        }
        if(root.right != null) {
            resultRoot += realRob(root.right.left, map) + realRob(root.right.right, map);
        }

        // 获取打劫子节点的结果
        int resultChild = realRob(root.left, map) + realRob(root.right, map);

        int result = Math.max(resultRoot, resultChild);
        map.put(root, result);
        return result;
    }
}
